package day_2022_7_to_8.day48;

import java.util.Stack;

/**
 * @author haomin
 * @date 2022/09/01 08:10
 **/
public class Day47_1_Num1475_FinalPrices {
    class Solution1 {
        public int[] finalPrices(int[] prices) {
            for(int i = 0; i < prices.length; ++i){
                for(int j = i+1; j < prices.length; ++j){
                    if(prices[i] >= prices[j]){
                        prices[i] -= prices[j];
                        break;
                    }
                }
            }
            return prices;
        }
    }
    class Solution {
        public int[] finalPrices(int[] prices) {
            Stack<Integer> stack = new Stack<>();
            int len = prices.length;
            int[] res = new int[len];
            for(int i = len-1; i >= 0; ++i){
                while(!stack.isEmpty() && stack.peek() > prices[i]) stack.pop();
                res[i] = stack.isEmpty() ? prices[i] : prices[i] - stack.peek();
                stack.push(prices[i]);
            }
            return res;
        }
    }

}